/*
 * Essential-C - Essential C Libraries for Developers
 * Copyright (c) 2004-2008 Tom Bradford <tom@tbradford.org>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a 
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 * DEALINGS IN THE SOFTWARE.
 */

#include <math.h>
#include <string.h>

#include "esc_list.h"
#include "esc_table.h"

#define INITIAL_LEVEL   4
#define INITIAL_SIZE    (1 << INITIAL_LEVEL)
#define BUCKET_SIZE     8
#define SPLIT_RATIO     0.80
#define HASH_PRIME      1610612741

/* Private Types and Variables ***********************************************/

typedef struct esc_table_entry_t esc_table_entry_t;
typedef struct esc_table_context_t esc_table_context_t;

/** Implementation type for Table instances */
struct esc_table_t {
    esc_table_hash_t* hashFunction;
    esc_table_compare_t* compareFunction;
    int level;
    int split;
    int tableSize;
    esc_list_t* buckets;
};

/** Implementation type for Table entry instances */
struct esc_table_entry_t {
    void* key;
    void* item;
};

/** Implementation type for Table iteration context instances */
struct esc_table_context_t {
    esc_table_t* table;
    esc_table_iterator_t* iterator;
    void* context;
};

/* Private Functions *********************************************************/

static int private_getHash(esc_table_t* table, void* key)
{
    return table->hashFunction(table, key) & 0x7FFFFFFF;
}

/*---------------------------------------------------------------------------*/

static int private_getBucket(esc_table_t* table, void* key)
{
    int hash = private_getHash(table, key);

    int bits = table->level;    
    int bucket = hash % (1 << bits);
    
    if ( bucket < table->split )
        bucket = hash % (1 << (bits +1));

    return bucket;
}

/*---------------------------------------------------------------------------*/

static int private_probeBucket(esc_table_t* table, esc_list_t* bucket, 
                               void* key)
{
    int size = esc_list_getSize(bucket);
    
    for ( int i = 0; i < size; i++ ) {
        esc_table_entry_t* entry = esc_list_getItem(bucket, i);
        
        if ( entry && table->compareFunction(table, key, entry->key) == 0 )
            return i;
    }
    
    return -1;
}

/*---------------------------------------------------------------------------*/

static esc_list_t* private_addBucket(esc_table_t* table)
{
    esc_mem_t* mem = esc_ptr_getMem(table);
    esc_list_t* bucket = esc_list_new(mem);
    
    esc_list_setClusterSize(bucket, BUCKET_SIZE);
    esc_list_addItem(table->buckets, bucket);
    
    return bucket;
}

/*---------------------------------------------------------------------------*/

static void private_entry_finalizer(esc_table_entry_t* entry)
{
    esc_ptr_release(entry->key);
    esc_ptr_release(entry->item);
}

/*---------------------------------------------------------------------------*/

static esc_table_entry_t* private_createEntry(esc_table_t* table, 
                                              void* key, void* item)
{
    esc_mem_t* mem = esc_ptr_getMem(table);    
    esc_table_entry_t* entry= esc_mem_malloc(mem, sizeof(esc_table_entry_t));

    entry->key = key;
    entry->item = item;
    
    esc_ptr_retain(key);
    esc_ptr_retain(item);
    
    esc_ptr_setDisposalFunction(entry, private_entry_finalizer);

    return entry;    
}

/*---------------------------------------------------------------------------*/

static void private_splitBucket(esc_table_t* table)
{
    private_addBucket(table);
    int bits = table->level;    

    int oldPos = table->split;    
    esc_list_t* oldBucket = esc_list_getItem(table->buckets, oldPos);

    for ( int i = 0; i < esc_list_getSize(oldBucket); ) {
        esc_table_entry_t* entry = esc_list_getItem(oldBucket, i);

        int hash = private_getHash(table, entry->key);
        int pos = hash % (1 << (bits + 1));
        
        if ( pos != oldPos ) {
            esc_list_t* newBucket = esc_list_getItem(table->buckets, pos);            
            esc_list_addItem(newBucket, entry);
            esc_list_removeIndex(oldBucket, i);
        }
        else 
            i++;
    }

    table->split++;
    
    if ( table->split == (1 << bits) ) {
        table->level++;
        table->split = 0;
    }
}

/*---------------------------------------------------------------------------*/

static esc_status_t private_bucketIterator(esc_list_t* bucket, 
                                           esc_table_entry_t* entry, 
                                           esc_table_context_t* ctx)
{
    esc_status_t result = ctx->iterator(ctx->table, entry->key, 
                                        entry->item, ctx->context);
                                        
    if ( result == ESC_TABLE_REMOVE ) {
        ctx->table->tableSize--;
        
        return ESC_LIST_REMOVE;
    }
    else
        return result;
}

/*---------------------------------------------------------------------------*/

static esc_status_t private_tableIterator(esc_list_t* buckets, 
                                          esc_list_t* bucket, 
                                          esc_table_context_t* ctx)
{
    return esc_list_iterate(bucket, private_bucketIterator, ctx);
}

/*---------------------------------------------------------------------------*/

static void private_table_finalizer(esc_table_t* table)
{
    esc_ptr_free(table->buckets);
}

/* Public Functions **********************************************************/

esc_table_t* esc_table_new(esc_mem_t* mem)
{
    esc_table_t* table = esc_mem_malloc(mem, sizeof(esc_table_t));
        
    table->hashFunction = esc_table_hash_string;
    table->compareFunction = esc_table_compare_string;
    table->level = INITIAL_LEVEL;
    table->split = 0;
    table->tableSize = 0;
    table->buckets = esc_list_new(mem);
    
    esc_list_setClusterSize(table->buckets, INITIAL_SIZE);

    for ( int i = 0; i < INITIAL_SIZE; i++ )
        private_addBucket(table);

    esc_ptr_setDisposalFunction(table, private_table_finalizer);

    return table;
}

/*---------------------------------------------------------------------------*/

int esc_table_hash_string(esc_table_t* table, char* key)
{
    int length = strlen(key);
    int hash = HASH_PRIME;

    for ( int i = 0; i < length; key++, i++ )
        hash ^= (hash << 5) + (*key) + (hash >> 2);
    
    return hash;
}

/*---------------------------------------------------------------------------*/

int esc_table_compare_string(esc_table_t* table, char* key1, char* key2)
{
    return strcmp(key1, key2);
}

/*---------------------------------------------------------------------------*/

void esc_table_setHashFunction(esc_table_t* table, 
                               esc_table_hash_t* hashFunction)
{
    table->hashFunction = hashFunction;
}

/*---------------------------------------------------------------------------*/

esc_table_hash_t* esc_table_getHashFunction(esc_table_t* table)
{
    return table->hashFunction;
}

/*---------------------------------------------------------------------------*/

void esc_table_setCompareFunction(esc_table_t* table, 
                                  esc_table_compare_t* compareFunction)
{
    table->compareFunction = compareFunction;
}

/*---------------------------------------------------------------------------*/

esc_table_compare_t* esc_table_getCompareFunction(esc_table_t* table)
{
    return table->compareFunction;
}

/*---------------------------------------------------------------------------*/

void esc_table_setItem(esc_table_t* table, void* key, void* item)
{
    if ( !key )
        return;

    if ( item ) {        
        int bucketNum = private_getBucket(table, key);
        esc_list_t* bucket = esc_list_getItem(table->buckets, bucketNum);
    
        int position = private_probeBucket(table, bucket, key);
        
        if ( position != -1 ) {
            esc_table_entry_t* entry = esc_list_getItem(bucket, position);
            
            esc_ptr_retain(item);            
            esc_ptr_release(entry->item);
            
            entry->item = item;
        }
        else {
            esc_table_entry_t* entry = private_createEntry(table, key, item);            
            esc_list_addItem(bucket, entry);
            table->tableSize++;
    
            float capacity = table->tableSize 
                             / (esc_list_getSize(table->buckets)
                             * BUCKET_SIZE);
                             
            if ( capacity > SPLIT_RATIO )
                private_splitBucket(table);
        }
    }
    else
        esc_table_removeItem(table, key);
}

/*---------------------------------------------------------------------------*/

void* esc_table_getItem(esc_table_t* table, void* key)
{
    if ( !key )
        return NULL;
        
    int bucketNum = private_getBucket(table, key);
    esc_list_t* bucket = esc_list_getItem(table->buckets, bucketNum);

    int position = private_probeBucket(table, bucket, key);
    
    if ( position != -1 ) {
        esc_table_entry_t* entry = esc_list_getItem(bucket, position);
        
        return entry->item;
    }
    else 
        return NULL;
}

/*---------------------------------------------------------------------------*/

void* esc_table_removeItem(esc_table_t* table, void* key)
{
    if ( !key )
        return NULL;
        
    int bucketNum = private_getBucket(table, key);
    esc_list_t* bucket = esc_list_getItem(table->buckets, bucketNum);

    int position = private_probeBucket(table, bucket, key);
    
    if ( position != -1 ) {
        esc_table_entry_t* entry = esc_list_getItem(bucket, position);
        esc_list_removeIndex(bucket, position);
        table->tableSize--;
        
        return entry->item;
    }
    else
        return NULL;
}

/*---------------------------------------------------------------------------*/

void esc_table_removeAll(esc_table_t* table)
{
    table->level = INITIAL_LEVEL;
    table->split = 0;    
    table->tableSize = 0;
    esc_list_removeAll(table->buckets);

    for ( int i = 0; i < INITIAL_SIZE; i++ )
        private_addBucket(table);
}

/*---------------------------------------------------------------------------*/

int esc_table_getSize(esc_table_t* table)
{
    return table->tableSize;
}

/*---------------------------------------------------------------------------*/

bool esc_table_isEmpty(esc_table_t* table)
{
    return table->tableSize == 0;
}

/*---------------------------------------------------------------------------*/

esc_status_t esc_table_iterate(esc_table_t* table, 
                               esc_table_iterator_t* iterator, void* context)
{
    esc_table_context_t ctx;
    ctx.table = table;
    ctx.iterator = iterator;
    ctx.context = context;
    
    return esc_list_iterate(table->buckets, private_tableIterator, &ctx);
}
